//
// Created by Lenovo on 2021/3/13.
//

#ifndef DATASTRUCTURE_C_GRAPH_H
#define DATASTRUCTURE_C_GRAPH_H

#include <iostream>

// 1、邻接矩阵（数组表示）
#define NODE_NUM 100
typedef struct AMGraph {
    char vexs[NODE_NUM];            //节点信息
    int arcs[NODE_NUM][NODE_NUM];   //边信息
    int vexnum, arcnum;  //节点数，边数
} AMGraph;

AMGraph *createAMGraph();

// 2、邻接表（链表表示）
// 类似hash的结构，一维数组（存储节点） + 节点指向链表（链表的节点存储边信息）
typedef struct ArcNode {
    std::string data;
    ArcNode *next;
} ArcNode;

typedef struct VexNode {
    std::string data;
    ArcNode *next;
} VexNode;

typedef struct ALGraph {
    VexNode vex[NODE_NUM];
    int vexnum, arcnum;  //节点数，边数
} ALGraph;

ALGraph *createALGraph();

// 3、十字链表

// 4、邻接多重表

//非递归深度遍历
void dfs(ALGraph *graph);
//递归深度遍历
void dfs2(ALGraph *graph);

//非递归广度遍历
void bfs(ALGraph *graph);
//递归广度遍历
void bfs2(ALGraph *graph);

// 拓扑排序：

// 关键路径：

#endif //DATASTRUCTURE_C_GRAPH_H
